#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None


class Solution:
    LEAST_INT = -2147483647

    def maxPathSum(self, root):
        one, two = self.rec_max_one_and_two_path(root)
        return two

    def rec_max_one_and_two_path(self, node):
        # one path: 从当前node作为根节点, 直通底部
        # two path: 左右两条path之和(分3种情况, 左边, 右边, 以当前节点作为path root中心)
        if not node:
            # return -1, -1
            return self.LEAST_INT, self.LEAST_INT

        left_one,  left_two  = self.rec_max_one_and_two_path(node.left)
        right_one, right_two = self.rec_max_one_and_two_path(node.right)
        # return max(left_one, right_one) + node.val, max(left_two, right_two, left_one + right_one + node.val)
        # return self._util_max_one(left_one, right_one, node.val), self._util_max_two(left_one, right_one, left_two, right_two, node.val)
        one_max = max(left_one, right_one, 0)
        two_max = max(
            left_two,
            right_two,
            left_one + right_one + node.val,
            left_one + node.val,
            right_one + node.val,
            node.val
        )
        return (one_max + node.val, two_max)


# class Solution:
#     def maxPathSum(self, root):
#         one, two = self.rec_max_one_and_two_path(root)
#         return two

#     def rec_max_one_and_two_path(self, node):
#         # one path: 从当前node作为根节点, 直通底部
#         # two path: 左右两条path之和(分3种情况, 左边, 右边, 以当前节点作为path root中心)
#         if not node:
#             return None, None

#         left_one,  left_two  = self.rec_max_one_and_two_path(node.left)
#         right_one, right_two = self.rec_max_one_and_two_path(node.right)
#         # return max(left_one, right_one) + node.val, max(left_two, right_two, left_one + right_one + node.val)
#         return self._util_max_one(left_one, right_one, node.val), self._util_max_two(left_one, right_one, left_two, right_two, node.val)

#     def _util_max_one(self, left_one, right_one, val):
#         # 之所以这么做, 而不是left和right是None时直接返回0: 是为了处理val是负数情况
#         if left_one is None and right_one is None:
#             return val

#         if (left_one is not None) and (right_one is not None):
#             # return max(left_one, right_one) + val
#             return max(left_one + val, right_one + val, val)
#         else:
#             # one = (left_one or right_one)     # NOTE: (0 or None) return None
#             # if left_one is None: one = right_one
#             # if right_one is None: one = left_one
#             one = self.or_value(left_one, right_one)

#             return max(one + val, val)

#     def _util_max_two(self, left_one, right_one, left_two, right_two, val):
#         # 之所以这么做, 而不是left和right是None时直接返回0: 是为了处理val是负数情况
#         # if val == 1:
#         #     print('match 1')
#         #     print(left_one, right_one)
#         #     print(left_two, right_two)
#         if left_two is None and right_two is None:
#             return val

#         if (left_two is not None) and (right_two is not None):
#             # print('=================== two =====================')
#             return max(left_two, right_two, left_one + right_one + val, right_one + val, left_one + val, val)
#         else:
#             # two = (left_two or right_two)
#             # one = (left_one or right_one)
#             two = self.or_value(left_two, right_two)
#             one = self.or_value(left_one, right_one)
#             return max(two, one+val)

#     def or_value(self, a, b):
#         if a is None: return b
#         if b is None: return a
#         assert False


def main():
    print("start main")
    s = Solution()

    root = TreeNode(-31)
    left = TreeNode(2)
    right = TreeNode(3)
    # root.left, root.right = left, right
    ret = s.maxPathSum(root)
    print(ret)


if __name__ == "__main__":
    main()
